package com.gitee.wsl.collections.deque.link


/**
 * This class provides a skeletal implementation of the [LinkedDeque] interface to minimize
 * the effort required to implement this interface.
 *
 * @author ben.manes@gmail.com (Ben Manes)
 * @param <E> the type of elements held in this collection
</E> */
 abstract class AbstractLinkedDeque<E> : AbstractCollection<E>(), LinkedDeque<E> {
    // This class provides a doubly-linked list that is optimized for the virtual machine. The first
    // and last elements are manipulated instead of a slightly more convenient sentinel element to
    // avoid the insertion of null checks with NullPointerException throws in the byte code. The links
    // to a removed element are cleared to help a generational garbage collector if the discarded
    // elements inhabit more than one generation.
    /**
     * Pointer to first node.
     * Invariant: (first == null && last == null) ||
     * (first.prev == null)
     */

    protected var _first: E? = null

    /**
     * Pointer to last node.
     * Invariant: (first == null && last == null) ||
     * (last.next == null)
     */
    protected var _last: E? = null

    /**
     * The number of times this deque has been *structurally modified*. Structural modifications
     * are those that change the size of the deque, or otherwise perturb it in such a fashion that
     * iterations in progress may yield incorrect results.
     */
    var modCount: Int = 0

    /**
     * Links the element to the front of the deque so that it becomes the first element.
     *
     * @param e the unlinked element
     */
    fun linkFirst(e: E) {
        val f = _first
        _first = e

        if (f == null) {
            _last = e
        } else {
            setPrevious(f, e)
            setNext(e, f)
        }
        modCount++
    }

    /**
     * Links the element to the back of the deque so that it becomes the last element.
     *
     * @param e the unlinked element
     */
    fun linkLast(e: E) {
        val l = _last
        _last = e

        if (l == null) {
            _first = e
        } else {
            setNext(l, e)
            setPrevious(e, l)
        }
        modCount++
    }

    /** Unlinks the non-null first element.  */
    fun unlinkFirst(): E? {
        val f = _first?:return null
        val next = getNext(f)
        setNext(f, null)

        _first = next
        if (next == null) {
            _last = null
        } else {
            setPrevious(next, null)
        }
        modCount++
        return f
    }

    /** Unlinks the non-null last element.  */
    fun unlinkLast(): E? {
        val l = _last?:return null
        val prev = getPrevious(l)
        setPrevious(l, null)
        _last = prev
        if (prev == null) {
            _first = null
        } else {
            setNext(prev, null)
        }
        modCount++
        return l
    }

    /** Unlinks the non-null element.  */
    fun unlink(e: E) {
        val prev = getPrevious(e)
        val next = getNext(e)

        if (prev == null) {
            _first = next
        } else {
            setNext(prev, next)
            setPrevious(e, null)
        }

        if (next == null) {
            _last = prev
        } else {
            setPrevious(next, prev)
            setNext(e, null)
        }
        modCount++
    }

    override fun isEmpty(): Boolean {
        return (_first == null)
    }

    fun checkNotEmpty() {
        if (isEmpty()) {
            throw NoSuchElementException()
        }
    }

    override val size: Int
        get() {
            var size = 0
            var e = _first
            while (e != null) {
                size++
                e = getNext(e)
            }
            return size
        }


    override fun clear() {
        var e = _first
        while (e != null) {
            val next = getNext(e)
            setPrevious(e, null)
            setNext(e, null)
            e = next
        }
        _last = null
        _first = _last
        modCount++
    }

    //abstract override fun contains(o: E): Boolean

    override fun isFirst(e: E): Boolean {
        return (e != null) && (e === _first)
    }

    override fun isLast(e: E): Boolean {
        return (e != null) && (e === _last)
    }

    override fun moveToFront(e: E) {
        if (e !== _first) {
            unlink(e)
            linkFirst(e)
        }
    }

    override fun moveToBack(e: E) {
        if (e !== _last) {
            unlink(e)
            linkLast(e)
        }
    }


    override fun peekOrNull(): E? {
        return peekFirst()
    }


    override fun peekFirst(): E? {
        return _first
    }

    override fun peekLast(): E? {
        return _last
    }

    override fun getFirst(): E {
        checkNotEmpty()
        return peekFirst()!!
    }

    override fun getLast(): E {
        checkNotEmpty()
        return peekLast()!!
    }

    override fun element(): E {
        return getFirst()
    }

    override fun offer(e: E): Boolean {
        return offerLast(e)
    }

    override fun offerFirst(e: E): Boolean {
        if (contains(e)) {
            return false
        }
        linkFirst(e)
        return true
    }

    override fun offerLast(e: E): Boolean {
        if (contains(e)) {
            return false
        }
        linkLast(e)
        return true
    }

    override fun add(element: E): Boolean {
        return offerLast(element)
    }

    override fun addFirst(e: E) {
        require(offerFirst(e))
    }

    override fun addLast(e: E) {
        require(offerLast(e))
    }


    override fun pollOrNull(): E? {
        return pollFirst()
    }


    override fun pollFirst(): E? {
        return if (isEmpty()) null else unlinkFirst()
    }


    override fun pollLast(): E? {
        return if (isEmpty()) null else unlinkLast()
    }

    override fun remove(): E? {
        return removeFirst()
    }

    override fun removeFirst(): E {
        checkNotEmpty()
        return pollFirst()!!
    }

    override fun removeFirstOccurrence(o: E): Boolean {
        return remove(o)
    }

    override fun removeLast(): E{
        checkNotEmpty()
        return pollLast()!!
    }

    override fun removeLastOccurrence(o: E): Boolean {
        return remove(o)
    }

    override fun removeAll(elements: Collection<E>): Boolean {
        var modified = false
        for (o in elements) {
            modified = modified or remove(o)
        }
        return modified
    }

    override fun remove(element: E): Boolean {
        if(contains(element)){
            unlink(element)
            return true
        }
        return false
    }

    override fun containsAll(elements: Collection<E>): Boolean {
        return super<LinkedDeque>.containsAll(elements)
    }

    override fun push(e: E) {
        addFirst(e)
    }

    override fun pop(): E? {
        return removeFirst()
    }

    override fun iterator(): LinkedDeque.PeekingIterator<E> {
        return object : AbstractLinkedIterator(_first) {
            override fun computeNext(): E? {
                return cursor?.let { getNext(it) }
            }
        }
    }

    override fun descendingIterator(): LinkedDeque.PeekingIterator<E> {
        return object : AbstractLinkedIterator(_last) {
            override fun computeNext(): E? {
                return cursor?.let { getPrevious(it) }
            }
        }
    }

    override fun addAll(elements: Collection<E>): Boolean {
        elements.forEach(::add)
        return true
    }

    override fun retainAll(elements: Collection<E>): Boolean {
        throw NotImplementedError()
    }


    internal abstract inner class AbstractLinkedIterator(start: E?) :
        LinkedDeque.PeekingIterator<E> {

        var previous: E? = null

        var cursor: E?

        var expectedModCount: Int

        /**
         * Creates an iterator that can can traverse the deque.
         *
         * @param start the initial element to begin traversal from
         */
        init {
            expectedModCount = modCount
            cursor = start
        }

        override fun hasNext(): Boolean {
            checkForComodification()
            return (cursor != null)
        }


        override fun peek(): E {
            return cursor?:throw NoSuchElementException()
        }

        override fun next(): E {
            if (!hasNext()) {
                throw NoSuchElementException()
            }
            previous = cursor
            cursor = computeNext()
            return previous!!
        }

        /** Retrieves the next element to traverse to or `null` if there are no more elements.  */
        //@Nullable
        abstract fun computeNext(): E?

        override fun remove() {
            checkNotNull(previous)
            checkForComodification()

            this@AbstractLinkedDeque.remove(previous!!)
            expectedModCount = modCount
            previous = null
        }

        /**
         * If the expected modCount value that the iterator believes that the backing deque should have
         * is violated then the iterator has detected concurrent modification.
         */
        fun checkForComodification() {
            if (modCount != expectedModCount) {
                throw ConcurrentModificationException()
            }
        }
    }
}
